Masala #0133

Xotira 16 MB Vaqt 1000 ms Qiyinchiligi 25 %

Olimpiada

O’zbekistonda m ta shahar bor (m = 2^k) va m ta shaharda jami n ta o’quvchi bor. Har bir o’quvchining o’zini bilim darajasi bor. (i – o’quvchining bilim darajasi a_i, ya’ni i – o’quvchi a_ita algoritm biladi). Ikkita o’quvchi o’zaro bellashishsa bilim darajasi yuqoriroq o’quvchi g’olib bo’ladi. (Barcha o’quvchilarning bilim darajalari har xil ekanligi kafolatlanadi).

O’quvchilar 2 ta olimpiadada qatnashishdi. (Beruniy va Al-Xorazmiy olimpiadasi)

Beruniy olimpiadasi tartibi quyidagicha (Futbol bo’yicha Jahon Chempionati tartibiga o’xshash):
Har bir shaharda alohida olimpiada o’tqaziladi. G’olib o’quvchi keyingi turga o’tadi (o’z shahridagi bilim darajasi eng yuqori bo’lgan o’quvchi). Keyingi turda 1-shaharlik o’quvchi 2-shaharlik o’quvchi bilan, 3-shaharlik o’quvchi 4-shaharlik o’quvchi bilan va hokazo bellashishadi. G’oliblar keyingi turga o’tib 1-juftlik g’olibi 2-juftlik g’olibi bilan va hokazo bellashishadi. Yakunda finalda yutgan o’quvchi 1-o’rin, yutqazgan 2-o’rin. Yarim finalda yutqazgan o’quvchilar 3-o’rin uchun bellashishadi. Yaxshiroq tushunish uchun izohga qarang.

Al-Xorazmiy olimpiadasi tartibi quyidagicha:
Barcha n ta o’quvchilar bir joyga to’planishadi va bilim darajasi eng yuqori bo’lgan o’quvchilarga mos ravishda 1, 2 va 3-o’rinlar beriladi.

Sizning vazifangiz ikkala olimpiadaning g’oliblarini aniqlash.

Kiruvchi ma'lumotlar:

Birinchi qatorda m va n kiritiladi. (4 ≤ m ≤ 2¹⁵, m ≤ n ≤ 2×10⁵)
Ikkinchi qatorda n ta natural sondan iborat a massiv - o’quvchilarning bilim darajalari kiritiladi (1 ≤ a[i] ≤ 10⁹)
Uchinchi qatorda ham n ta natural sondan iborat c massiv kiritiladi. (c[i] – i-o’quvchining qaysi shahardanligi, 1 ≤ c[i] ≤ m)

Har bir shaharda kamida bitta o’quvchi yashashi kafolatlanadi.

Chiquvchi ma'lumotlar:

Birinchi qatorda 3ta natural son. 1-olimpiadaning g’oliblarini raqamlarini chiqaring. Avval 1 - o’rin egasining raqami, keyin 2, keyin 3-o’rinning raqamini chiqaring.
Ikkinchi qatorda ham xuddi shu tartibda 2-olimpiadaning g’oliblarini chiqaring.

Misollar

#	input.txt	output.txt
1	8 14 16 8 29 12 15 20 5 32 42 85 22 53 11 21 6 7 3 4 4 5 1 8 1 2 4 7 5 3	10 12 3 10 12 9

Izoh:

1 – shaharlik o’quvchilar – {7, 9}
2 – shaharlik o’quvchilar – {10}
3 – shaharlik o’quvchilar – {3, 14}
4 – shaharlik o’quvchilar – {4, 5, 11}
5 – shaharlik o’quvchilar – {6, 13}
6 – shaharlik o’quvchilar – {1}
7 – shaharlik o’quvchilar – {2, 12}
8 – shaharlik o’quvchilar – {8}

Avval Beruniy olimpiadasi g’oliblarini topamiz.
1 – shaharning olimpiadasi g’olibi 9-o’quvchi. Sababi uning bilim darajasi 42, 7-o’quvchining bilim darajasi esa 5. 9-o’quvchi keying turga o’tadi.
2 – shaharning olimpiadasi g’olibi 10-o’quvchi chunki shaharda undan boshqa o’quvchi yo’q.
Shunday qilib o’z shahrining g’olib o’quvchilari – {9, 10, 3, 11, 6, 1, 12, 8}. Keyingi turda 9-o’quvchi 10-o’quvchi bilan, 3-o’quvchi 11-o’quvchi bilan va h.k. bellashishadi. Yarim finalga kelgan o’quvchilar {10, 3, 6, 12}. Birinchi yarim finalda 10 va 3-o’quvchilar bellashishadi. Ikkinchi yarim finalda 6 va 12. Finalga chiqishdi – {10, 12}. 3-o’rin uchun bahsda bellashadi {3, 6}. Shunday qilib 1-o’rin – 10, 2-o’rin – 12 va 3-o’rin – 3-raqamli o’quvchilar.

Endi Al-Xorazmiy olimpiadasi g’oliblari:
1-o’rin – 10-raqamli o’quvchi
2-o’rin – 12-raqamli o’quvchi
3-o’rin – 9-raqamli o’quvchi

Telegram Facebook

Yechimini yuborish

Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin